#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/6/11 14:12
# @USER    : Shengji He
# @File    : ValidSudoku.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from typing import List


class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        """
        Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to
        the following rules:
            - Each row must contain the digits 1-9 without repetition.

            - Each column must contain the digits 1-9 without repetition.

            - Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

        The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

        Example 1:

        Input:

        [
          ["5","3",".",".","7",".",".",".","."],

          ["6",".",".","1","9","5",".",".","."],

          [".","9","8",".",".",".",".","6","."],

          ["8",".",".",".","6",".",".",".","3"],

          ["4",".",".","8",".","3",".",".","1"],

          ["7",".",".",".","2",".",".",".","6"],

          [".","6",".",".",".",".","2","8","."],

          [".",".",".","4","1","9",".",".","5"],

          [".",".",".",".","8",".",".","7","9"]
        ]

        Output: true

        Example 2:

        Input:

        [

          ["8","3",".",".","7",".",".",".","."],

          ["6",".",".","1","9","5",".",".","."],

          [".","9","8",".",".",".",".","6","."],

          ["8",".",".",".","6",".",".",".","3"],

          ["4",".",".","8",".","3",".",".","1"],

          ["7",".",".",".","2",".",".",".","6"],

          [".","6",".",".",".",".","2","8","."],

          [".",".",".","4","1","9",".",".","5"],

          [".",".",".",".","8",".",".","7","9"]

        ]

        Output: false

        Explanation: Same as Example 1, except with the 5 in the top left corner being
            modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

        Note:
            - A Sudoku board (partially filled) could be valid but is not necessarily solvable.

            - Only the filled cells need to be validated according to the mentioned rules.

            - The given board contain only digits 1-9 and the character '.'.

            - The given board size is always 9x9.

        :param board: List[List[str]]
        :return: bool
        """
        boxes = {i: {str(j): 0 for j in range(1, 10)} for i in range(9)}
        columns = {i: {str(j): 0 for j in range(1, 10)} for i in range(9)}
        for row in range(9):
            row_dict = {str(j): 0 for j in range(1, 10)}
            for column in range(9):
                if board[row][column] != '.':
                    row_dict[board[row][column]] += 1
                    columns[column][board[row][column]] += 1
                    boxes[row // 3 * 3 + column // 3][board[row][column]] += 1
                    if row_dict[board[row][column]] > 1 or columns[column][board[row][column]] > 1 or \
                            boxes[row // 3 * 3 + column // 3][board[row][column]] > 1:
                        return False
        return True


if __name__ == '__main__':
    S = Solution()
    board = [
        ["8", "3", ".", ".", "7", ".", ".", ".", "."],
        ["6", ".", ".", "1", "9", "5", ".", ".", "."],
        [".", "9", "8", ".", ".", ".", ".", "6", "."],
        ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
        ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
        ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
        [".", "6", ".", ".", ".", ".", "2", "8", "."],
        [".", ".", ".", "4", "1", "9", ".", ".", "5"],
        [".", ".", ".", ".", "8", ".", ".", "7", "9"]
    ]

    print(S.isValidSudoku(board))
    print('done')
